Combination sum IV

Time: O(NxLogN+NxT); Space: O(T); medium

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example 1:

Input: nums = [1, 2, 3], target = 4

Output: 7

Explanation:

  • The possible combination ways are:

    [1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]

  • Note that different sequences are counted as different combinations.

  • Therefore the output is 7.

Example 2:

Input: nums = [1, 2], target = 4

Output: 5

Explanation:

  • The possible combination ways are:

    [1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]

Follow up:

  • What if negative numbers are allowed in the given array?

  • How does it change the problem?

  • What limitation we need to add to the question to allow negative numbers?

[3]:

class Solution1(object):
    """
    Time: O(NxLogN+NxT),T is the value of target.
    Space: O(T)
    """
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0] * (target+1)
        dp[0] = 1
        nums.sort()

        for i in range(1, target+1):
            for j in range(len(nums)):
                if nums[j] <= i:
                    dp[i] += dp[i - nums[j]]
                else:
                    break

        return dp[target]

[4]:

s = Solution1()

nums = [1, 2, 3]
target = 4
assert s.combinationSum4(nums, target) == 7

nums = [1, 2]
target = 4
assert s.combinationSum4(nums, target) == 5